import java.util.*;

public class SolutionInterview8_2 {
    public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
        Queue<int[]> queue=new LinkedList<>();
        Map<List<Integer>,List<Integer>> pre=new HashMap<>();
        queue.offer(new int[]{0,0});
        if (obstacleGrid[0][0]==1){
            return new ArrayList<>();
        }
        int[][] visit=new int[obstacleGrid.length][obstacleGrid[0].length];
        while (!queue.isEmpty()){
            int[] p=queue.poll();
            if (p[0]==obstacleGrid.length-1 && p[1]==obstacleGrid[0].length-1){
                List<List<Integer>> ans=new ArrayList<>();
                List<Integer> now=Arrays.asList(p[0],p[1]);
                while (now.get(0)!=0 || now.get(1)!=0){
                    ans.add(0,now);
                    now=pre.get(now);
                }
                ans.add(0,Arrays.asList(0,0));
                return ans;
            }
            if (p[0]+1<obstacleGrid.length && obstacleGrid[p[0]+1][p[1]]!=1 && visit[p[0]+1][p[1]]==0){
                visit[p[0]+1][p[1]]=1;
                queue.offer(new int[]{p[0]+1,p[1]});
                pre.put(Arrays.asList(p[0]+1,p[1]),Arrays.asList(p[0],p[1]));
            }
            if (p[1]+1<obstacleGrid[0].length && obstacleGrid[p[0]][p[1]+1]!=1 && visit[p[0]][p[1]+1]==0){
                visit[p[0]][p[1]+1]=1;
                queue.offer(new int[]{p[0],p[1]+1});
                pre.put(Arrays.asList(p[0],p[1]+1),Arrays.asList(p[0],p[1]));
            }
        }
        return new ArrayList<>();
    }

    public static void main(String[] args) {
        System.out.println(new SolutionInterview8_2().pathWithObstacles(new int[][]{{0,0,0},{0,1,0},{0,0,0}}));
    }
}
